package com.wyp168.leetcode;


import java.util.*;

/**
 * @ClassName GroupAnagrams
 * @Description TODO 将异位词分组
 *              TODO 异位词： 由相同的字母 不同的排列顺序组成不同含义的单词
 * @Author wyp168
 * @Date 2022/8/17 08:41
 */
public class GroupAnagrams {
    public static void main(String[] args) {
        GroupAnagrams groupAnagrams = new GroupAnagrams();
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(groupAnagrams.groupAnagrams(strs));
    }

    /**
     * 基本思路：先将每个字符串取出来，转换成字符数组格式，对数组进行排序，有序字符数组如果相等
     *          则说明两个单词是异位词
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            //先将字符串转换为字符数组
            char[] chars = str.toCharArray();
            //对字符数组进行排序
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}
